package main

import (
	"fmt"
	"math/rand"
)

func GradeSort(grade []int) {
	arr := make([]int, 101)
	// 每一个成绩装到对应的桶中
	for _, v := range grade {
		arr[v]++
	}
	// 把成绩装回去
	index := 0
	for i, v := range arr {
		if v == 0 {
			continue
		} else {
			// 如果桶不为空,也就是说arr[i]不为空
			// 意思就是成绩为 i 的人有多少个
			// 所以我们把这些成绩装回grade数组中去
			for v != 0 {
				v--
				grade[index] = i
				index++
			}
		}
	}
}

// 对arr[l...r]部分进行partition操作
// 返回p, 使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p]
func partition(arr []int, l, r int) int {
	// 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
	// rand.Seed(time.Now().Unix())
	// randIndex := rand.Int()%(r-l+1) + l
	// arr[l], arr[randIndex] = arr[randIndex], arr[l]

	v := arr[l]
	j := l
	for i := l + 1; i <= r; i++ {
		if arr[i] < v {
			j++
			// arr[j], arr[i] = arr[i], arr[j]
		}
	}
	arr[l], arr[j] = arr[j], arr[l]

	return j
}

func QuickSort(arr []int, l, r int) {
	if l >= r {
		return
	}
	p := partition(arr, l, r)
	QuickSort(arr, l, p-1)
	QuickSort(arr, p+1, r)
}

func main() {
	grades := make([]int, 10)
	for i := 0; i < len(grades); i++ {
		grades[i] = rand.Intn(101)
	}
	fmt.Println(grades)

	GradeSort(grades)

	fmt.Println(grades)

	var arr []int
	arr = []int{5, 3, 4, 2}
	fmt.Println(arr)
	QuickSort(arr, 0, len(arr)-1)
	fmt.Println(arr)
}
